package Offer;

/**
 * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
 */

/*
    思路: 逆序很容易想到的就是迭代；或者是修改指针的指向
*/
public class T24_reverseList {
//    迭代 三指针
    public ListNode reverseList3(ListNode head){
        if (head == null) {
            return head;
        }
        ListNode cur, pre, tmp;
        cur = head;
        pre = null;
        tmp = cur.next;

        while (tmp != null) {
            cur.next = pre;
            pre = cur;
            cur = tmp;
            tmp = tmp.next;
        }
        cur.next = pre;
        return cur;
    }


    //==================================递归1==========================================
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode p = head;
        while (p.next != null) { //找到正序链表的最后一个结点作为逆序链表的首节点（这里有点繁琐，还要多一次遍历）
            p = p.next;
        }

        ListNode node = dfs(head);
        node.next = null;
        return p;
    }

    ListNode dfs(ListNode node) {
        if (node.next == null) {
            return node;
        }
        ListNode preNode = dfs(node.next);
        preNode.next = node;
        return node;
    }




    //==================================递归2==========================================
    public ListNode reverseList2(ListNode head) {
        return recur(head, null);       //调用递归并返回
    }

    /***
     *
     * @param cur 当前遍历的结点
     * @param pre 逆序链表中充当cur的前驱
     * @return 整个过程的返回值都是逆序链表的头结点
     */
    private ListNode recur(ListNode cur, ListNode pre) {
        if (cur == null) return pre;         // 终止条件

        ListNode res = recur(cur.next, cur); // 递归后继节点 返回的是逆序链表中的前驱结点

        cur.next = pre;                      // 修改节点引用指向

        return res;                          // 返回反转链表的头节点（整个递归过程返回的res都是正序链表的最后一个结点）最后返回给上层的就是逆序的头结点
    }

}
